package kg.aibek.projecteuler.p51;

import java.util.ArrayList;
import java.util.List;

import kg.aibek.helper.Sequence;

public class Problem64 {
	public void solve() {
		int count = 0;
		for (int i = 2; i <= 10000; i++) {
			int x = (int) Math.sqrt(i);
			if (x * x == i)
				continue;

			int period = findPeriod(sequence(i));
			if (period % 2 == 1) {
				count++;
			}
		}
		System.out.println(count);
	}

	private List<Integer> sequence(int number) {
		List<Integer> list = new ArrayList<Integer>();

		int x = (int) Math.sqrt(number);

		int den = 1;
		int num = 0;

		int count = 0;
		while (count++ <= 1000) {
			int a = getMax(x, num, den);
			num = Math.abs(num - a * den);
			den = (number - num * num) / den;

			list.add(a);
		}

		return list;
	}

	private int getMax(int x, int num, int den) {
		int p = 0;

		while (p * den - num <= x) {
			p++;
		}
		return p - 1;
	}

	private int findPeriod(List<Integer> list) {
		List<Sequence> sequences = new ArrayList<Sequence>();
		for (int i = 1; i <= 490; i++) {
			sequences.add(new Sequence(i));
		}

		for (int i = 1; i < list.size(); i++) {
			List<Sequence> rem = new ArrayList<Sequence>();
			for (Sequence seq : sequences) {
				if (!seq.addNumber(list.get(i))) {
					rem.add(seq);
				}
			}
			sequences.removeAll(rem);
		}

		int min = Integer.MAX_VALUE;
		for (Sequence seq : sequences) {
			if (seq.getSeq().size() < min) {
				min = seq.getSeq().size();
			}
		}
		return min;
	}

	public static void main(String[] args) {
		Problem64 p = new Problem64();
		p.solve();
	}
}
